package basic.courseLearn07.problem;

import basic.courseLearn07.Graph;
import basic.courseLearn07.Node;
import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

//宽度优先遍历
public class BreadthFirstTraversal {

    public void traversal(Node root){
        //1. 判断root是否为空
        if(root == null) return;
        //2. 创建队列，set集合
        Queue<Node> queue = new LinkedList<>();
        HashSet<Node> set = new HashSet<>();
        //3. 将root节点放入队列
        queue.add(root);
        set.add(root);
        //4. 遍历队列
        while(!queue.isEmpty()){
            //4.1 出队
            Node node = queue.poll();
            System.out.print(node.value+" ");
            //4.2 循环遍历node的邻居
            for (Node tempNode : node.nexts) {
                if (tempNode!= null &&!set.contains(tempNode)){
                    //入队，加入set之中
                    queue.add(tempNode);
                    set.add(tempNode);
                }
            }
        }


    }

    @Test
    public void test(){
        Graph graph = new Graph();
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node1.getNexts().add(node2);
        node1.getNexts().add(node4);
        node1.getNexts().add(node6);
        node2.getNexts().add(node1);
        node2.getNexts().add(node3);
        node3.getNexts().add(node2);
        node3.getNexts().add(node5);
        node3.getNexts().add(node6);
        node4.getNexts().add(node1);
        node5.getNexts().add(node3);
        node6.getNexts().add(node1);
        node6.getNexts().add(node3);
        HashMap<Integer, Node> map = new HashMap<>();
        map.put(1, node1);
        map.put(2, node2);
        map.put(3, node3);
        map.put(4, node4);
        map.put(5, node5);
        map.put(6, node6);
        graph.setNodes(map);
        traversal(node1);

    }









}
